import java.util.HashMap;
import java.util.Map;

/**
 * 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
 * <p>
 * 实现 LFUCache 类：
 * <p>
 * LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
 * int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
 * void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。
 * <p>
 * 为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
 * <p>
 * 当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
 * <p>
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * <p>
 * <p>
 * https://leetcode.cn/problems/lfu-cache/description/
 * 讲解：https://www.bilibili.com/video/BV1rv4y1H7o6?spm_id_from=333.788.player.switch&vd_source=36dbb0f6eb577254888df3bf9b4ce456&p=190
 * LFU 缓存算法
 *
 * @author liuzhaoqiang
 */
public class LFUCache {
    static class Node {
        int key;
        int value;
        Node pre;
        Node next;
        int freq;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node(){

        }
    }

    static class DoubleLinkedList {
        int size;
        Node head;
        Node tail;

        public DoubleLinkedList() {
            head = tail = new Node();
            head.next = tail;
            tail.pre = head;
        }

        // a<--->b<--->c
        public void removeNode(Node node) {
            Node a = node.pre;
            Node c = node.next;
            a.next = c;
            c.pre = a;
            size--;
        }

        public Node removeLast() {
            Node lastNode = tail.pre;
            removeNode(lastNode);
            return lastNode;
        }

        /**
         * head-->node-->tail
         *
         * @param node
         */
        public void addFirst(Node node) {
            Node next = head.next;
            head.next = node;
            node.pre = head;

            node.next = next;
            next.pre = node;
        }
    }

    private Map<Integer, Node> keyValueMap = new HashMap<>();
    private Map<Integer, DoubleLinkedList> freqMap = new HashMap<>();
    private int capacity;
    private int minFreq = 1;//最小使用频度

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    /**
     * key 不存在 返回-1
     * key 存在 返回 value 值 增加节点使用频度，将其转移到频度+1 的链表当中
     *
     * @param key
     * @return
     */
    public Integer getValue(int key) {
        if (!keyValueMap.containsKey(key)) {
            return -1;
        }
        Node node = keyValueMap.get(key);
        //删除频度
        freqMap.get(node.freq).removeNode(node);
        if (freqMap.get(node.freq).size == 0 && node.freq == minFreq) {
            minFreq++;
        }
        //更新使用频率
        node.freq++;
        //更新 freqMap
        DoubleLinkedList doubleLinkedList = freqMap.get(node.freq);
        if (doubleLinkedList == null) {
            doubleLinkedList = new DoubleLinkedList();
            freqMap.put(node.freq, doubleLinkedList);
        }
        doubleLinkedList.addFirst(node);
        return node.value;
    }

    /**
     * 更新：
     * 将节点的 value 更新，增加节点的使用频率，将其转移到平率+1 的链表当中
     * 插入
     * 检查是否超过容量 若超过 淘宝 minFreq 链表的最后节点
     * 创建新的节点 放入 kvMap 并加入平率 1 的双向链表
     *
     * @param key
     * @param value
     */
    public void putValue(int key, int value) {
        if (keyValueMap.containsKey(key)) {
            Node node = keyValueMap.get(key);
            DoubleLinkedList doubleLinkedList = freqMap.get(node.freq);
            doubleLinkedList.removeNode(node);
            if (doubleLinkedList.size == 0 && node.freq == minFreq) {
                minFreq++;
            }
            node.freq++;
            DoubleLinkedList link = freqMap.get(node.freq);
            if (link == null) {
                link = new DoubleLinkedList();
                freqMap.put(node.freq, link);
            }
            link.addFirst(node);
            node.value = value;
        } else {
            //判断是否超过了容量
            if(capacity <= keyValueMap.size()){
                Node lastNode = freqMap.get(minFreq).removeLast();
                keyValueMap.remove(lastNode.key);
            }
            Node node = new Node(key, value);
            node.freq = 1;
            keyValueMap.put(key, node);
            DoubleLinkedList doubleLinkedList = freqMap.get(node.freq);
            if (doubleLinkedList == null) {
                doubleLinkedList = new DoubleLinkedList();
                freqMap.put(node.freq, doubleLinkedList);
            }
            doubleLinkedList.addFirst(node);
            minFreq = 1;
        }

    }
}
